// Thor - High Performance C++ containers and algorithm library.
//
// Copyright (c) 2010 Su Shi. All rights reserved.
//
// Author: Su Shi <carmack.shi [at] gmail.com>

#include <gtest/gtest.h>

#include <thor_ttf_heap.h>

typedef thor::TTFHeap<int> IHeap;

TEST(TTFHeap, Insert) {
  IHeap heap;

  EXPECT_TRUE(heap.Empty());

  for (int i = 128; i >= 1; i /= 2)
    heap.Insert(i);

  EXPECT_EQ(8, heap.Size());

  EXPECT_EQ(1, *heap.Minimum());

  EXPECT_FALSE(heap.Empty());

}

TEST(TTFHeap, Decrease) {
  IHeap heap;

  EXPECT_TRUE(heap.Empty());

  for (int i = 128; i >= 1; i /= 2)
    heap.Insert(i);

  IHeap::Iterator it = heap.Minimum();

  EXPECT_EQ(1, *it);

  heap.Decrease(it, -128);

  it = heap.Minimum();

  EXPECT_EQ(-128, *it);
}

TEST(TTFHeap, Delete) {
  IHeap heap;

  EXPECT_TRUE(heap.Empty());

  for (int i = 128; i >= 1; i /= 2)
    heap.Insert(i);

  IHeap::Iterator it = heap.Minimum();

  EXPECT_EQ(1, *it);

  heap.Delete(it);

  it = heap.Minimum();

  EXPECT_EQ(2, *it);

  heap.Delete(it);

  it = heap.Minimum();

  EXPECT_EQ(4, *it);
}

TEST(TTFHeap, ExtractMinimum) {
  IHeap heap;

  EXPECT_TRUE(heap.Empty());

  for (int i = 128; i >= 1; i /= 2)
    heap.Insert(i);

  IHeap::Iterator it = heap.Minimum();

  EXPECT_EQ(1, *it);

  heap.ExtractMinimum();

  it = heap.Minimum();

  EXPECT_EQ(2, *it);

}

TEST(TTFHeap, Union) {
  IHeap heap_x, heap_y;

  for (int i = 128; i >= 1; i /= 2)
    heap_x.Insert(i);

  EXPECT_EQ(1, *heap_x.Minimum());


  for (int i = -128; i < 0; i /= 2)
    heap_y.Insert(i);

  EXPECT_EQ(-128, *heap_y.Minimum());


  heap_x.Union(&heap_y);

  EXPECT_TRUE(heap_y.Empty());

  EXPECT_EQ(-128, *heap_x.Minimum());
}